package lib

//link to 918
func init() {
	Probs = append(Probs, Problem{
		Num:         53,
		Discription: "最大连续子数组之和",
		Level:       2,
		Labels: map[string]int{
			"动态规划": 1,
			"空间降维": 1,
		},
	})
}

func MaxSubArray(nums []int) int {
	maxSum := nums[0]
	//preSum表示以前一个元素结尾的子数组的最大和
	preSum := nums[0]
	for i := 1; i < len(nums); i++ {
		if preSum <= 0 {
			preSum = nums[i]
		} else {
			preSum += nums[i]
		}
		maxSum = max(maxSum, preSum)
	}

	return maxSum
}
